package com.lw.leetcode.arr.a;

/**
 * Created with IntelliJ IDEA.
 * a
 * str
 * 1967. 作为子字符串出现在单词中的字符串数目
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/18 9:51
 */
public class NumOfStrings {

    public static void main(String[] args) {

        NumOfStrings test = new NumOfStrings();

        // 54
        String[] strs = {"e", "ulhjriiikuwwi", "odtbmiyiv", "iiku", "o", "nao", "ilrbdhfvndjaxohexcynpgocoqorifjngaurokumcqqkirqp", "zmt", "tuxulhjriiikuwwibjpodtbmiyiv", "lhjriiikuwwibjpodtbmiyi", "qjnwwkfqhztiyqayiabjjzyqhumh", "lhjriiikuwwibjpodtbmiyiv", "oyaloibpkqpyubftinknjraptsuqgejucpfigc", "fdqvajkfornietcdvxltbktlkg", "bcxslqwrjaabvywpynzfojetmnnwrurimjgwl", "ncvvyhbznxrxoonfrzfmecfdnrvikffpvrc", "gxvzmtuxulhjriiikuwwibjpodtbmiyi", "ozuwzgetoddakvjwiwzocpwpiavcyclxhlguhfqtpbk", "ktwqukguxobakxvbitkkdemvlmqypd", "gxvzmtuxulhjri", "xulhjriiiku", "sjemhhtbqastmbtbvsfnuygqfypmmi", "gqfmyqbjcvuxsjdaeffwthlelb", "kuwwibjpodtbmiyivse", "ydwiabsimbkdwmsvgp", "ixrzoktohtadgblem", "uicfykignmptxodjd", "kecqujgjynq", "sruqpwjevngokrbyi", "rijyzrhrygxvzmtuxulhjriii", "gsljxjrmkzbwaqdgmwysnblp", "arkmbbafkziemddeqripnyjoavmoaxtn", "gxhijktottj", "ibjpodtbmiyivse", "j", "qzvmjstehwibuqcqlzdam", "ikuwwibjpodt", "mnrp", "pduagikyudhcvdnqoaadqvvmhluywfsstqnawfmq", "vse", "iyiv", "miyivs", "qdfrbkhffkksgtjpnbgvqtrnigbnoacmqkepllouhqpgskpupy", "wxbqfmzvmmffwtwjhjpuitcfmknnuwdtamtutiukmpsxzu", "odtbmiyi", "hrygxvzmtuxulhjriiiku", "yzrhrygxvzmtuxu", "se", "gixgfjtunbltzcwgkrheavilcvektnsizvrrabmysx", "hjriiikuwwibj", "ahaeorlnaqkk", "gvnyr", "tynqzmrvdjaznuji", "jbwybcttaspwsbieawybfqxsiwxulwkouezkhbauadatb", "uwwibjpodt", "gxv", "zrhrygxvzmtuxulhjriiikuwwib", "wivvuywmwchszzctw", "lijcroypqr", "mrx", "m", "ygngqghhza", "riiikuwwibjpodtbmiyivs", "tymtjqykindweexrfztizyagijnxntrcrcy", "vse", "kntxszudqpmtlrxzspcfivbrwonejzywv", "ygxvzmtuxulh", "wsnnrijyzrhrygxvzmtuxulhjriiik", "zpymedyxskwqddvxlycxvq", "qdkm", "gxvzmtuxu", "snnrijyzrhrygxvzmtuxulhjriiikuwwibjpo", "iyivserr", "yzrhrygxvzmt", "rygxvzmtuxulhjrii", "snnrijyzrhrygxvzmtuxul", "gxvzmtuxulhjriiikuwwibjpodtbmiyivserr", "kuwwibjpodt", "ibjpodtbmiy", "mtuxulhjriii", "zrhrygxvzmtu", "qxjvgdyuqt", "rygxv", "gnwmvzqhrodzqdvdexgupqbzogcpmtfq", "oleibiotmojkqexnnlx", "dtb", "jjividhfhdixcvyduyunoiiipyvi", "podtb", "jpodtbmiyi", "iiku", "od", "kuwwibjpodtb", "b", "irugjrzvsfp", "wsnnrijyzrhrygxvzmtuxulhjrii", "jriiikuwwibjpodtbmi"};
        String str = "wsnnrijyzrhrygxvzmtuxulhjriiikuwwibjpodtbmiyivserr";

        int i = test.numOfStrings(strs, str);
        System.out.println(i);
    }

    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        char[] c1 = word.toCharArray();
        for (String pattern : patterns) {
            if (find(c1, pattern)) {
                count++;
            }
        }
        return count;
    }

    private boolean find(char[] c1, String b) {
        int m = c1.length;
        int n = b.length();
        int j = 0;
        char[] c2 = b.toCharArray();
        int[] arr = find(c2);
        for (int i = 0; i < m; i++) {
            if (j == -1 || c1[i] == c2[j]) {
                j++;
            } else {
                j = arr[j];
                i--;
            }
            if (j == n) {
                return true;
            }
        }
        return false;
    }

    private int[] find(char[] c2) {
        int n = c2.length;
        int[] arr = new int[n];
        arr[0] = -1;
        int j = -1;
        for (int i = 0; i < n - 1; i++) {
            if (j == -1 || c2[i] == c2[j]) {
                j++;
                arr[i + 1] = j;
            } else {
                j = arr[j];
                i--;
            }
        }
        return arr;
    }

}
